package algorithm;

import java.util.ArrayList;
import java.util.List;

public class QuickSort {

	public static void main(String[] args) {
//		int[] arr = {
//				12, 54, 5, 3, 56, 3, 7, 33, 6
//		};
//		List<Integer> list = toList(arr);
//		print(list);
//		sort(list, 0, list.size());
//		print(list);
		
		List<Integer> list = new ArrayList<Integer>();
		for(int i=0; i<100; i++) {
			int random =(int) (Math.random()*1000);
			list.add(random);
		}
		print(list);
		sort(list, 0, list.size());
		print(list);
	}
	
	public static void sort(List<Integer> list, int start, int end) {
		if(end - start < 1) {
			throw new RuntimeException("至少需要1个数");
		}
		int x = list.get(start);
		List<Integer> newList = new ArrayList<Integer>();
		listAdd(newList, list, 0, start);
		//小于x的放x左边
		for(int i=start + 1; i< end; i++) {
			if(list.get(i) <= x) {
				newList.add(list.get(i));
			}
		}
		int xIndex = newList.size();
		//放x
		newList.add(x);
		//大于x的放x右边
		for(int i=start + 1; i< end; i++) {
			if(list.get(i) > x) {
				newList.add(list.get(i));
			}
		}
		listAdd(newList, list, end, list.size());
		for(int i=start; i< end; i++) {
			list.set(i, newList.get(i));
		}
		
//		for(int i=0; i< newList.size(); i++) {
//			list.set(i+start, newList.get(i));
//		}
//		print(list);
		if(xIndex - start >=2) {
			sort(list, start , xIndex);
		}
		if(end - (xIndex + 1) >=2) {
			sort(list, xIndex+1, end);
		}
	}
	
	public static List<Integer> toList(int[] a) {
		List<Integer> list = new ArrayList<Integer>();
		for(int i=0; i< a.length; i++) {
			list.add(a[i]);
		}
		return list;
	}
	public static void print(List<Integer> list) {
		for(int i : list) {
			System.out.print(i + " ");
		}
		System.out.print("\n");
	}
	
	public static void listAdd(List<Integer> list1, List<Integer> list2, int start, int end) {
		for(int i=start; i< end; i++) {
			list1.add(list2.get(i));
		}
	}

}
